'''
https://leetcode.cn/problems/maximum-frequency-stack/description/
'''

class Node:
    def __init__(self, value = -1, next=None):
        self.value = value
        self.next = next

class FreqStack:

    def __init__(self):
        self.stack = [Node(-1)]
        self.max_freq = 0
        self.freq_map = {}

    def push(self, val: int) -> None:
        freq = self.freq_map[val] if val in self.freq_map else 0
        freq += 1
        self.freq_map[val] = freq
        node = Node(val)
        if freq > self.max_freq:
            # 新起一层
            self.max_freq = freq
            self.stack.append(node)
        else:
            # 已经存在这一层了
            head = self.stack[freq]
            node.next = head
            self.stack[freq] = node

    def pop(self) -> int:
        stack_top = self.stack[self.max_freq]
        return_val = stack_top.value
        if stack_top.next:
            self.stack[self.max_freq] = stack_top.next
        else:
            self.max_freq -= 1
            self.stack.pop()
        self.freq_map[return_val] -= 1  # 可以检查是否del，但没必要
        return return_val
